#include "../tools.h"

// 回溯，选择
// 如果左括号数多，则选左右括号都可以
// 如果相等，只能选左括号
class Solution {
public:
    void trace(vector<string>& res, string route, int left_l, int left_r){ // 可用的左括号、右括号
        if(left_l == 0 && left_r == 0){
            res.emplace_back(route);
        }

        int left = left_l + left_r;
        if(left_l > 0) trace(res, route + "(", left_l - 1, left_r);
        if(left_r > 0 && left_r > left_l) trace(res, route + ")", left_l, left_r - 1);
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n == 0) return res;

        trace(res, "", n, n);
        return res;


    }
};



int main(int argc, char const *argv[])
{
    
    int n = 1;
    Solution s;
    vector<string> res = s.generateParenthesis(n);
    show(res);
    return 0;
}
